#ifndef STRUCTS_H
#define STRUCTS_H

/**
 * estrutura que representa o
 * elemento armazenado na arvore
 */
typedef struct tipoItem {
  int chave;
}Item;

/*
 * estrutura que representa a
 * arvore binaria e um ponteiro da mesma
 */
typedef struct no* apontador;
struct no {
  Item valor;
  apontador esq;
  apontador dir;
};

/**
 * inicializa campos de um ponteiro para uma arvore
*/
void inicializa(apontador *raiz){
  *raiz = (apontador) malloc(sizeof(struct no));
  (*raiz)->valor.chave = -1;
  (*raiz)->esq = NULL;
  (*raiz)->dir = NULL;
}

/*
 * retorna ponteiro para arvore seguro para uso
 * apontador minha_raiz = cria_raiz();
*/
apontador cria_raiz(){
  apontador raiz;
  inicializa(&raiz);
  return raiz;
}

/**
 * insere novo elemento na arvore
*/
void insere(Item x, apontador* no) {
  if ((*no) == NULL) {
     (*no) = cria_raiz();
     (*no)->valor = x;
  }
  else if ((*no)->valor.chave == -1)
    (*no)->valor = x;
  else if (x.chave < (*no)->valor.chave)
    insere(x, &((*no)->esq));
  else insere(x, &((*no)->dir));
}

/*
 * verifica se a arvore esta vazia
*/
int vazia(apontador raiz){
  if(raiz->valor.chave == -1)
    return 1;
  else
    return 0;
}

/**
 * imprime elemento
*/
void visita_raiz(apontador no) {
  printf("%d ", no->valor.chave);
}

/*
 * imprime elementos da arvore na ordem (R E D)
*/
void pre_ordem(apontador no) {
  if (no != NULL) {
     visita_raiz(no);
     pre_ordem(no->esq);
     pre_ordem(no->dir);
  }
}

/**
 * imprime elementos da arvore na ordem (E R D)
*/
void em_ordem(apontador no) {
  if (no != NULL) {
     em_ordem(no->esq);
     visita_raiz(no);
     em_ordem(no->dir);
  }
}

/*
 * imprime elementos da arvore na ordem (E D R)
*/
void pos_ordem(apontador no) {
  if (no != NULL) {
     pos_ordem(no->esq);
     pos_ordem(no->dir);
     visita_raiz(no);
  }
}

/**
 * pesquisa recursivamente se um elemento esta na arvore
 * retorna 1 caso encontre o valor ou 0 caso contrario
*/
int pesquisa(Item valor,apontador raiz){
  if(raiz->valor.chave == valor.chave)
    return 1;
  else if(valor.chave < raiz->valor.chave && raiz->esq != NULL)
    return pesquisa(valor,raiz->esq);
  else if(valor.chave > raiz->valor.chave && raiz->dir != NULL)
    return pesquisa(valor,raiz->dir);
  else
    return 0;
}

/*
 * remove elemento e substitui pelo seu filho de
 * maior valor
*/
void antecessor(apontador q, apontador *r) {
  if ((*r)->esq != NULL)
     antecessor(q, &((*r)->esq));
  else {
     q->valor = (*r)->valor;
     q = *r;
     *r = (*r)->dir;
     free(q);
  }
}

/**
 * pesquisa recursivamente se um elemento esta na arvore
 * e o remove
*/
void retira(Item x, apontador* no, int *operacao) {
  apontador aux;
  if ((*no) == NULL)
     *operacao = 0;
  else if (x.chave < (*no)->valor.chave)
    retira(x, (&(*no)->esq), operacao);
       else if (x.chave > (*no)->valor.chave)
         retira(x, (&(*no)->dir), operacao);
      else {
         *operacao = 1;
         if ((*no)->dir == NULL) {
      aux = *no;
      *no = (*no)->esq;
      free(aux);
         }
         else if ((*no)->esq == NULL) {
           aux = *no;
           *no = (*no)->dir;
           free(aux);
              }
        else antecessor((*no), (&(*no)->dir));
      }
}

/*
 * remove todos os elementos da arvore
*/
void esvazia(apontador *raiz){
  if (vazia((*raiz)) == 0){
    int op;
    if((*raiz)->esq != NULL)
      retira((*raiz)->esq->valor,&((*raiz)->esq),&op);
    if((*raiz)->dir != NULL)
      retira((*raiz)->dir->valor,&((*raiz)->dir),&op);
    (*raiz)->esq = NULL;
    (*raiz)->dir = NULL;
    (*raiz)->valor.chave = -1;
  }
}

#endif //STRUCTS_H
